package org.shj.algorithm.dhsjjg.mintree;

/**
 * 普里姆算法解决：
 *  有N个点，任意两个点间的连线权值不等(也可能两点间无连线)，找出 n-1 条边，使得N个点能连通，
 *  并且使得连线权值的总和最小。
 *  实例： minTree.png
 * @author huangjian
 *
 */
public class Prim {

	//用最大值来表示两个点之间没有连线
	public static int INFINITY = Integer.MAX_VALUE; 
	
	public static void main(String[] args){
		Graph g = new Graph();
		int min, i, j, k;
		int MAXVEX = g.getDots().length; //顶点个数最大值
		int[] arcvex = new int[MAXVEX];      //保存相关顶点的下标
		int[] lowcost = new int[MAXVEX];     //保存相关顶点间边的权值
		
		lowcost[0] = 0; //初始化第一个权值为0，即 V0加入生成树
		arcvex[0] = 0; //初始化第一个顶点下标为 0
		
		for(i = 1; i < g.getDots().length ; i++){
			lowcost[i] = g.getArc()[0][i];   //将V0顶点与之有边的权值存入数组
			arcvex[i] = 0;                   //初始化都为V0的下标
		}
		
		for(i = 1; i < g.getDots().length ; i++){
			min = INFINITY;      //初始化最小权值
			j = 1 ; k = 0;
			while(j < g.getDots().length){
				if(lowcost[j] != 0 && lowcost[j] < min){ //如果权值不为0且小于min
					min = lowcost[j];
					k = j;								 //将当前最小值的下标存入k
				}
				j++;
			}
			System.out.println("(" + g.getDots()[arcvex[k]] + "," + g.getDots()[k] + ")"); //打印当前顶点边中权值最小边
			
			lowcost[k] = 0;   //将当前顶点的权值设置为0， 表示此顶点已经完成任务
			for(j = 1 ; j < g.getDots().length ; j++){
				if(lowcost[j] != 0 && g.getArc()[k][j] < lowcost[j]){  //若下标为k顶点各边权值 小于此前之些顶点未被加入生树权值
					lowcost[j] = g.getArc()[k][j];                     //将较小权值存入lowcost
					arcvex[j] = k;									   //将下标为k的顶点存入arcvex
				}
			}
		}
	}
}


